#include <vector>

//希尔排序（本质上是插入排序）-----平均时间复杂度为O(nlog(n))----空间复杂度O(1),不稳定
void Shell_sort(vector<int> &nums){
    int i,j,k;
    for(i = nums.size()/2;i > 0;i/=2){
        for(j = i;j < nums.size();j++){
            int temp = nums[j];
            if(nums[j] < nums[j-i]){
                for(k = j-i;k >= 0&&nums[k] > temp;k=k-i){
                    nums[k+i] = nums[k];  
                }
                nums[k+i] = temp;
            }
        }
    }
}